#pragma once

#include <algorithm>
#include <vector>

namespace solution_077
{

class Solution
{
public:
    std::vector< std::vector<int> > combine(int n, int k)
    {
        std::vector<int> path;
        backtrack(path, 1, n, k);
        return m_combs;
    }

private:
    void backtrack(std::vector<int>& path, int first, int n, int k)
    {
        int curr_len = path.size();
        int rest_len = k - curr_len;
        if (curr_len == k) {
            m_combs.push_back(path);
            return;
        }

        for (int i = first; i <= (n - rest_len + 1); ++i) {
            path.push_back(i);
            backtrack(path, i + 1, n, k);
            path.pop_back();
        }
    }

    std::vector< std::vector<int> > m_combs;
};

}  /* namespace solution_077 */
